import copy, math
from bisect import bisect_left
from consts import *

TIME_MAT = {}	# TIME_MAT[start_loc][end_loc] = start_loc -> end_loc travel time

WAIT = 0
ROUTE = 1
global_opt = {WAIT:None, ROUTE:None}	# {'WAIT' : wait_time, 'ROUTE' : [route_sequence]}

loc_dict = {}	# dictionary containing all location objects by their location id
start_loc = None	# start location by id
root = None	# root node for branch and bound tree



def index(lst, target):
    try:
    	return lst.index(target)
    except ValueError:
    	return -1



def distance(loc_id1, loc_id2):
	return TIME_MAT[loc_id1][loc_id2]

def filterCountable(list_city_ids):
	return [city for city in loc_dict.values() if city.getID() in list_city_ids and city.isCountable()]

def isValidLoc(city_id, selected, cur_size):
	valid_type = loc_dict[city_id].getSize() > 0 or (loc_dict[city_id].getSize() < 0 and loc_dict[city_id].getAssocLoc() == None) or (loc_dict[city_id].getSize() < 0 and loc_dict[city_id].getAssocLoc() in selected)
	valid_size = cur_size + loc_dict[city_id].getSize() <= CAPACITY and cur_size + loc_dict[city_id].getSize() >= 0
	return valid_type and valid_size

def computeSizeActive(remaining):
	return sum([math.fabs(city.getSize()) for city in filterCountable(remaining)])

def computeWaitActive(remaining):
	return sum([city.getWait()*math.fabs(city.getSize()) for city in filterCountable(remaining)])

def computeLB(current_loc, remaining, current_wait):
	shortest_dist_cur = float('inf')	# some unreasonably big number
	shortest_edge_cur = [] 				# list containing shortest edge to remaining locs if there are any remaining locs # (0,0,0) # (weight, ID_A, ID_B)
	for other_id in remaining:
		if distance(current_loc,other_id) < shortest_dist_cur:
			shortest_dist_cur = distance(current_loc,other_id)
			shortest_edge_cur = [(shortest_dist_cur, current_loc, other_id)]

	short_edge_list = []	# includes duplicates
	for city_id in remaining:	# find shortest edge for each city
		shortest_dist = float('inf')	# some unreasonably big number
		shortest_edge = (0,0,0)		# (weight, ID_A, ID_B)
		for other_id in remaining:
			if city_id != other_id:
				if distance(city_id,other_id) < shortest_dist:
					shortest_dist = distance(city_id,other_id)
					shortest_edge = (shortest_dist, city_id, other_id)
		short_edge_list.append(shortest_edge)
	short_edge_list.sort()	# sort edges by travel time (i < i+1)

	short_edge_list = shortest_edge_cur + short_edge_list[:-1]

	#print str(current_loc) + "\t" + str(shortest_edge_cur)

	tmp_remaining = [city.getID() for city in sorted(loc_dict.values()) if city.getID() in remaining]	# sort cities by size (i < i+1) 
	tmp_size_active = computeSizeActive(remaining) # number of active people: sum size of PICKUPS with unknown dropoffs, DROPOFFS, VANS
	tmp_wait = current_wait
	#(-1)*sum([city.getSize() for city in self.city_dict.values() if city.getID() in tmp_remaining and city.getSize() < 0] )	# sum weights of all dropoffs	
	
	#for edge in short_edge_list:
	#	tmp_wait += edge[0] * tmp_size_active	# increase wait_time by edge_time for van_size + remaining_pickups_size
	#	if loc_dict[tmp_remaining[0]].getSize() < 0:	# if dropoff then number of affected people decreases, otherwise number of affected people is unchanged
	#		tmp_size_active += loc_dict[tmp_remaining[0]].getSize() 	# if drop off then weight is neg so size decreases
	#	tmp_remaining.pop(0)
	#print str(current_loc) + "\t" + str(short_edge_list)
	for edge in short_edge_list: #while len(short_edge_list) > 0:
		tmp_wait += edge[0] * tmp_size_active	# update total wait
		#print str(current_loc) + "\t" + str(tmp_wait) + "\t" + str(edge[0]) + "\t" + str(tmp_size_active)

		loc_visited_idx = 0		# by default we visit the first loc in tmp_remaining
		loc_obj = loc_dict[tmp_remaining[0]]	# object for first loc in tmp_remaining
		#print "\t" + str(current_loc) + "\t" + str(loc_obj.getSize())
		if loc_obj.getSize() < 0:	# if dropoff then number of affected people decreases, otherwise number of affected people is unchanged
			assoc_idx = index(tmp_remaining,loc_obj.getAssocLoc())
			#print "\t" + str(current_loc) + "\t" + str(assoc_idx) + "\t" + str(loc_obj.getAssocLoc())
			#print "\t" + str(current_loc) + "\t" + str(tmp_remaining) + "\t" + str(loc_obj.getAssocLoc())

			if loc_obj.getAssocLoc() == None or assoc_idx == -1:	# this dropoff does not have an unselected associated pickup
				# visit this dropoff loc as per default
				# dropoffs reduce the active size
				tmp_size_active += loc_obj.getSize() # since dropoff then weight is neg so size decreases
			else:	# this dropoff has an assoc pickup and the assoc pickup has not been selected 
				# visit assoc pickup instead of dropoff
				# pickups do not alter active size
				loc_visited_idx = assoc_idx

		tmp_remaining.pop(loc_visited_idx)	# remove the visited location from remaining
		
	return tmp_wait



class BBNode(object):
	def __init__(self, current_loc, remaining, selected = [], current_wait = 0, current_size = 0):
		self.current_loc = current_loc
		self.remaining = copy.deepcopy(remaining)	# location IDs only
		self.selected = copy.deepcopy(selected)
		self.children = []

		#self.remaining_countable = filterCountable(self.remaining, self.city_dict)

		self.current_wait = current_wait
		self.current_size = current_size
		self.lower_bound = computeLB(self.current_loc, self.remaining, self.current_wait)

		#print self

	def expand(self):
		global global_opt
		#self.children = sorted([BBNode(self.city_dict, city_id, filter(lambda loc_id : loc_id != city_id, self.remaining), self.selected + [city_id], self.current_wait + self.city_dict[self.current_loc].distance(self.city_dict[city_id]) * (-1)*sum([city.getSize() for city in self.city_dict.values() if city.getID() in self.remaining and ((city.getSize() > 0 and city.getAssocLoc() == None) or city.getSize < 0)]), self.current_size + self.city_dict[city_id].getSize()) for city_id in self.remaining if (self.city_dict[city_id].getSize() > 0 or (self.city_dict[city_id].getAssocLoc() != None and self.city_dict[city_id].getAssocLoc() in self.selected)) and self.current_size + self.city_dict[city_id].getSize() <= CAPACITY and self.current_size + self.city_dict[city_id].getSize() >= 0])
		self.children = sorted(	[ 
								BBNode( city_id 
										,filter(lambda loc_id : loc_id != city_id, self.remaining)
										,self.selected + [city_id] 
										,self.current_wait +
											distance(self.current_loc, city_id) 
											* computeSizeActive(self.remaining)
										,self.current_size + loc_dict[city_id].getSize()
										) 
								for city_id in self.remaining 
								if 	isValidLoc(city_id, self.selected, self.current_size)
								] )

		pruned_children = []
		for child in self.children:
			if global_opt[WAIT] != None and global_opt[WAIT] < child.getLB():
				#print len(child.selected)
				continue
			else:
				pruned_children.append(child)

		#print len(self.children), len(pruned_children)
		#print len(self.selected), len(self.children), len(pruned_children)
		self.children = pruned_children

		return len(self.children) > 0

	def getChildren(self):
		return self.children

	def getLB(self):
		return self.lower_bound

	def getWait(self):
		return self.current_wait

	def getSize(self):
		return self.current_size

	def getLocation(self):
		return self.current_loc

	def getRoute(self):
		return self.selected

	def __lt__(self, other):
		return self.lower_bound < other.getLB()

	def __le__(self, other):
		return self.lower_bound <= other.getLB()

	def __eq__(self, other):
		return self.lower_bound == other.getLB()

	def __str__(self):
		return "loc: %d\t\tlb: %d\nsize: %d\t\twait: %d\nsel: %s\nrem: %s\n" % (self.current_loc, self.lower_bound, self.current_size, self.current_wait, ",".join(map(str,self.selected)), ",".join(map(str,self.remaining)))





def setLocations(locs):
		global start_loc
		global root
		global loc_dict
		global global_opt

		start_loc = copy.deepcopy(locs[0])	# Van size
		loc_dict = dict(zip([loc.getID() for loc in locs], copy.deepcopy(locs)))	# location dictionary {city_id : city}
		global_opt = {WAIT:None, ROUTE:None}	# {'WAIT' : wait_time, 'ROUTE' : [route_sequence]}

		root_current_loc = start_loc.getID()
		root_remaining = [city.getID() for city in locs[1:]]	# all location ids excluding Van
		root_selected = []	
		root_size = start_loc.getSize()	# size of the Van
		root_wait = computeWaitActive(root_remaining)	# PICKUPs with unknown dropoffs, DROPOFFs (have associated PICKUPs), VANs 
		#sum([city.getWait()*math.fabs(city.getSize()) for city in filterCountable(root_remaining, loc_dict)])	
		root = BBNode(root_current_loc, root_remaining, root_selected, root_wait, root_size)

def expand(cur):
		global global_opt

		#print "call"

		#if DEBUG:
		#	print cur.selected, cur.remaining, cur.current_wait, cur.lower_bound

		if global_opt[WAIT] != None and global_opt[WAIT] < cur.getLB():
			return

		if cur.expand() == False:
			if global_opt[WAIT] == None or (cur.getWait() < global_opt[WAIT] and len(cur.getRoute()) >= len(global_opt[ROUTE])) or len(cur.getRoute()) > len(global_opt[ROUTE]):
			#if global_opt[WAIT] == None or cur.getWait() < global_opt[WAIT]:
				global_opt[WAIT] = cur.getWait()
				global_opt[ROUTE] = copy.deepcopy(cur.getRoute())
				#print cur.selected
			return

		for branch in cur.getChildren():
			#print branch.selected, branch.lower_bound
			expand(branch)

		return

def optimizeRoute(locs):
	setLocations(locs)
	expand(root)

def printRoute():
		print ",".join([",".join(loc_dict[city_id].getPHPID()) for city_id in global_opt[ROUTE]])

		if DEBUG:	#debug: include location detail in route printout
			print "wait:", global_opt[WAIT]
			print
			print "route detail:"
			for loc in global_opt[ROUTE]:
				print loc_dict[loc]
